from typing import List
from collections import deque


digit_map = {
    "2": "abc",
    "3": "def",
    "4": "ghi",
    "5": "jkl",
    "6": "mno",
    "7": "pqrs",
    "8": "tuv",
    "9": "wxyz",
}


class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        result_list = []
        cur_res = ""
        for i in digits:
            for j in digit_map[i]:
                cur_res.append(j)
        return []

    # def backtrace(self, cur_len: int,target_len:int, result: List, cur_res: str):
    #     if cur_len == target_len:
    #         result.append(cur_res)
    #         return
    #     for i in digit_map["2"]:
    #         backtrace(cur_len+1, target_len, result, cur_res)
    #     pass
